package com.camus.algorithm.impl;

import com.camus.algorithm.SubsetAlgorithm4Int;
import com.camus.utils.NumberUtils;

/**
 * 简单循环算法求目标和的子集
 * 
 * @author jie.deng
 *
 */
public class SubsetAlgorithmOfLoop4Int implements SubsetAlgorithm4Int {

	@Override
	public int[] findSubsetOfTargetSum(int[] candidateArr, int target) {
		int[] subsetArr = null;
		int len = candidateArr.length;
		assert len <= 31;
		// 复杂度是2的n次方
		for (int i = 1; i < NumberUtils.pow(2, len); i++) {
			boolean[] flagArr = NumberUtils.toBoolArr(i, len);
			int sum = 0;
			for (int j = 0; j < len; j++) {
				if (flagArr[j]) {
					sum += candidateArr[j];
				}
			}
			if (sum == target) {
				int size = 0;
				for (int j = 0; j < len; j++) {
					if (flagArr[j]) {
						size++;
					}
				}
				subsetArr = new int[size];
				for (int j = len - 1; j >= 0; j--) {
					if (flagArr[j]) {
						subsetArr[--size] = candidateArr[j];
					}
				}
				break;
			}
		}
		return subsetArr;
	}

}
